package com.lw.leetcode.dp.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1626. 无矛盾的最佳球队
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/29 17:30
 */
public class BestTeamScore {


    public static void main(String[] args) {
        BestTeamScore test = new BestTeamScore();
        //
        // 34
        int[] scores = {1, 3, 5, 10, 15};
        int[] ages = {1, 2, 3, 4, 5};

        // 16
//        int[] scores = {4,5,6,5};
//        int[] ages = {2,1,2,1};

        // 6
//        int[] scores = {1, 2, 3, 5};
//        int[] ages = {8, 9, 10, 1};

        // 10
//        int[] scores = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
//        int[] ages = {811, 364, 124, 873, 790, 656, 581, 446, 885, 134};

        // 27
//        int[] scores = {9, 2, 8, 8, 2};
//        int[] ages = {4, 1, 3, 3, 5};

        int i = test.bestTeamScore(scores, ages);
        System.out.println(i);
    }

    public int bestTeamScore(int[] scores, int[] ages) {
        int length = scores.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = (ages[i] << 20) + scores[i];
        }
        Arrays.sort(arr);
        int max = 0;
        int[] counts = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            int a = arr[i] >> 20;
            int s = arr[i] & 0XFFFFF;
            counts[i] = s;
            for (int j = i + 1; j < length; j++) {
                int s1 = arr[j] & 0XFFFFF;
                if ((arr[j] >> 20) == a || s1 >= s) {
                    counts[i] = Math.max(counts[i], counts[j] + s);
                }
            }
            max = Math.max(max, counts[i]);
        }
        return max;
    }

}
